package com.matt.mergesort;

import java.util.Arrays;

public class MergeSort
{
    /**
     * Method to sort (view merge sort) a given array.
     * @param array Array to sort
     * @return Sorted array
     */
    public int[] sort(int[] array)
    {
        //System.out.println("sort(), array: " + Arrays.toString(array));
        
        int size = array.length;
        if(size < 2)
            return array;
        
        int[] left, right;
        int midIndex = array.length / 2;
        
        // Initialize / copy arrays
        left = Arrays.copyOfRange(array, 0, midIndex);
        right = Arrays.copyOfRange(array, midIndex, size);
        //System.out.println("left: " + Arrays.toString(left) + ", right: " + Arrays.toString(right));
        
        // Recursive sort
        left = sort(left);
        right = sort(right);
        
        // Merge
        return merge(left, right);
    }

    /**
     * Method to merge to arrays into a new array containing the contents of the two arrays
     * passed in.
     * 
     * @param left Left array to merge
     * @param right Right array to merge
     * @return New merged array
     */
    private int[] merge(int[] left, int[] right)
    {
        //System.out.println("merge(), left: " + Arrays.toString(left) + ", right: " + Arrays.toString(right));
        int totalElements = left.length + right.length;
        int[] newArr = new int[totalElements];
        
        int index = 0, leftIndex = 0, rightIndex = 0;
        
        // Loop over all the elements
        while(index < totalElements)
        {
            if(leftIndex < left.length && rightIndex < right.length)
            {
                if(left[leftIndex] <= right[rightIndex])
                {
                    newArr[index] = left[leftIndex];
                    index++;
                    leftIndex++;
                }
                else
                {
                    newArr[index] = right[rightIndex];
                    index++;
                    rightIndex++;
                }
            }
            // Left array has values remaining
            else if(leftIndex < left.length)
            {
                while(leftIndex < left.length)
                {
                    newArr[index] = left[leftIndex];
                    index++;
                    leftIndex++;
                }
            }
            // Right array have values remaining.
            else if(rightIndex < right.length)
            {
                while(rightIndex < right.length)
                {
                    newArr[index] = right[rightIndex];
                    index++;
                    rightIndex++;
                }
            }
        }
        
        //System.out.println("merge() return newArr: " + Arrays.toString(newArr));
        return newArr;
    }
}
